/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import org.jheaps.Heap
import org.junit.Assert
import org.junit.Test
import java.io.*
import java.math.BigInteger
import java.util.*

class BigIntegerRadixHeapTest {
    @Test
    fun testBug2() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.ZERO, BigInteger.valueOf(100))
        h.insert(BigInteger.ZERO)
        Assert.assertEquals(BigInteger.ZERO, h.findMin())
        Assert.assertEquals(BigInteger.ZERO, h.deleteMin())
        h.insert(BigInteger.valueOf(15))
        Assert.assertEquals(BigInteger.valueOf(15), h.findMin())
    }

    @Test
    fun test() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.ZERO, SIZE)

        for (i in 0 until SIZE.toLong()) {
            h.insert(BigInteger.valueOf(i))
            Assert.assertEquals(BigInteger.valueOf(0), h.findMin())
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), i + 1)
        }

        for (i in SIZE.toLong() - 1 downTo 0) {
            Assert.assertEquals(h.findMin(), BigInteger.valueOf(SIZE.toLong() - i - 1))
            h.deleteMin()
        }
    }

    @Test
    fun testVerySmall() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.valueOf(29), BigInteger.valueOf(36))

        h.insert(BigInteger.valueOf(29L))
        h.insert(BigInteger.valueOf(30L))
        h.insert(BigInteger.valueOf(31L))
        h.insert(BigInteger.valueOf(30L))
        h.insert(BigInteger.valueOf(33L))
        h.insert(BigInteger.valueOf(36L))
        h.insert(BigInteger.valueOf(35L))

        Assert.assertEquals(h.size(), 7)
        Assert.assertEquals(h.findMin().toLong(), 29L)
        Assert.assertEquals(h.size(), 7)
        Assert.assertEquals(h.deleteMin().toLong(), 29L)
        Assert.assertEquals(h.size(), 6)
        Assert.assertEquals(h.findMin().toLong(), 30L)
        Assert.assertEquals(h.deleteMin().toLong(), 30L)
        Assert.assertEquals(h.findMin().toLong(), 30L)
        Assert.assertEquals(h.deleteMin().toLong(), 30L)
        Assert.assertEquals(h.findMin().toLong(), 31L)
        Assert.assertEquals(h.deleteMin().toLong(), 31L)
        Assert.assertEquals(h.findMin().toLong(), 33L)
        Assert.assertEquals(h.deleteMin().toLong(), 33L)
        Assert.assertEquals(h.findMin().toLong(), 35L)
        Assert.assertEquals(h.deleteMin().toLong(), 35L)
        Assert.assertEquals(h.findMin().toLong(), 36L)
        Assert.assertEquals(h.deleteMin().toLong(), 36L)
        Assert.assertEquals(h.size(), 0)
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testSortRandomSeed1() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.valueOf(0), SIZE.add(BigInteger.ONE))

        val generator = Random(1)

        val a = LongArray(SIZE.toInt())
        for (i in 0 until SIZE.toInt()) {
            a[i] = (SIZE.toLong() * generator.nextDouble()).toLong()
        }
        Arrays.sort(a)
        for (i in 0 until SIZE.toInt()) {
            h.insert(BigInteger.valueOf(a[i]))
        }

        var prev: BigInteger? = null
        var cur: BigInteger
        while (!h.isEmpty) {
            cur = h.findMin()
            h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testClear() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.ZERO, BigInteger.valueOf(15))

        for (i in 0..14L) {
            h.insert(BigInteger.valueOf(i))
        }

        h.clear()
        Assert.assertEquals(0L, h.size())
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testMultipleDeleteMin() {
        val step = BigInteger.valueOf(7)
        val min = BigInteger.ZERO
        val max = BigInteger.valueOf(100000)

        val h: Heap<BigInteger> = BigIntegerRadixHeap(min, max)

        h.insert(min)
        var cur = min
        while (cur.compareTo(max) < 0) {
            Assert.assertEquals(cur, h.findMin())
            if (cur.add(step).compareTo(max) >= 0) {
                break
            }
            val newCur = cur.add(step)
            h.insert(newCur)
            Assert.assertEquals(cur, h.findMin())
            Assert.assertEquals(cur, h.deleteMin())
            cur = newCur
        }
    }

    @Test
    fun testMonotoneOkOnLastDeleted() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.ZERO, BigInteger.valueOf(100))
        h.insert(BigInteger.valueOf(100L))
        Assert.assertEquals(BigInteger.valueOf(100L), h.findMin())
        h.insert(BigInteger.valueOf(99L))
        Assert.assertEquals(BigInteger.valueOf(99L), h.findMin())
    }

    @Test(expected = IllegalArgumentException::class)
    fun testMonotoneNotOkOnLastDeleted() {
        val h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.ZERO, BigInteger.valueOf(100))
        h.insert(BigInteger.valueOf(100L))
        h.deleteMin()
        h.insert(BigInteger.valueOf(99L))
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction() {
        BigIntegerRadixHeap(BigInteger.ZERO.subtract(BigInteger.ONE), BigInteger.valueOf(100))
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction1() {
        BigIntegerRadixHeap(BigInteger.valueOf(100), BigInteger.valueOf(99))
    }

    /*@Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction2() {
        BigIntegerRadixHeap(null, BigInteger.valueOf(99))
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIllegalConstruction3() {
        BigIntegerRadixHeap(BigInteger.valueOf(99), null)
    }*/

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializable() {
        var h: Heap<BigInteger> = BigIntegerRadixHeap(BigInteger.ZERO, BigInteger.valueOf(15))

        for (i in 0..14L) {
            h.insert(BigInteger.valueOf(i))
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as Heap<BigInteger>

        for (i in 0..14L) {
            Assert.assertEquals(15 - i, h.size())
            Assert.assertEquals(BigInteger.valueOf(i), h.findMin())
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    companion object {
        private val SIZE: BigInteger = BigInteger.valueOf(100000)
    }
}
